/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Yacc;

import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.*;
/**
 *
 * @author Administrator
 */
public class FirstSet {
    public Set<String> []firstset;              //保存first集的元素
    public String []nonterminal;                //保存非终结结点
    public int linenumber;              		//保存非终结结点个数
    private int tmplinenumber;                  //如果文件中一共有5行，则tmplinenumber = 4 ???
    private String []tmpterminal;               //中间结果，拆分符号左边的内容
    private String []tmpnonterminal;                //拆分符号右边的内容
    private String []tmppartnonterminal;                //拆分符号右边第一部分的内容
    private Set<String> []tmpallnonterminal;
    private Set<String> endcharacter;

    public FirstSet() {
        firstset = new TreeSet[1000];
        nonterminal = new String[1000];
        linenumber = 0;
        tmpterminal = new String[1000];
        tmpnonterminal = new String[1000];
        tmppartnonterminal = new String[1000];
        tmpallnonterminal = new TreeSet[1000];
        tmplinenumber = 0;
        endcharacter = new TreeSet();
        for(int i = 0; i < 1000; i++) { 
            firstset[i] = new TreeSet(); 
            tmpallnonterminal[i] = new TreeSet();
        }
    }



    // interface for other class
    private int getNonterminalNum(){return linenumber+1;}
    private int getOrderProLines(){return tmplinenumber;}
    public Set<String>[] getFirst(){ // first
        Set<String>[] first = Arrays.copyOf(firstset, getNonterminalNum());
        return first;
    }
    public String[] getNonterminal(){ // 非终结符
        String[] nontml =  Arrays.copyOf(nonterminal,getNonterminalNum());
        return nontml;
    }
    public String[] getOrderProLeft(){
        String[] proLeft = Arrays.copyOf(tmpterminal,getOrderProLines());
        return proLeft;
    }
    public String[] getOrderProRight(){
        return tmpnonterminal;
    }





    public void init() {
        String s;
        try {
            String filePath = "D:\\gittest\\polychrome\\if-else.bnf";
            LineNumberReader br = new LineNumberReader(new FileReader(filePath));
            for( s = br.readLine(); s!= null; s = br.readLine() ) {             //读取一行
                linenumber = br.getLineNumber() - 1;
                System.out.println("当前行数为：" + linenumber + " 当前行的内容为" + s);
                String []stringArray;
                String []stringArray1;
                stringArray = new String[1000];
                stringArray1 = new String[1000];
                stringArray = s.split("::=", 2);               //将每个表达式按“::=”划分为两部分
                nonterminal[linenumber] = stringArray[0].trim();               //将表达式左边的部分保存到terminal数组中
                stringArray[1] = stringArray[1].replace("\"|\"", "\"$\"");              //如果遇到“|”的情况，则替换为“$”,以避免被当成|来处理
                if (stringArray[1].indexOf('|') != -1) {                //将表达式右边的部分以“|”划分，将每一部分保存到tmpnonterminal[tmplinenumber]
                    stringArray1 = stringArray[1].split("\\|");
                    //System.out.println(s + "的右边应划分为" + stringArray1.length + "块");
                    for(int i =0; i < stringArray1.length; i++) {
                        tmpterminal[tmplinenumber] = nonterminal[linenumber];
                        stringArray1[i] = stringArray1[i].replace("\"$\"", "\"|\"");                //将“$”重新替换成“|”
                        tmpnonterminal[tmplinenumber] = stringArray1[i].trim();
                        tmplinenumber++;
                    }
                } else {
                    tmpterminal[tmplinenumber] = nonterminal[linenumber];
                    tmpnonterminal[tmplinenumber] = stringArray[1].trim();
                    tmplinenumber++;
                }
            }
            maketmppartnonterminal();
            Islegal();
            makefirstset();
        }
        catch(IOException e) {
            e.printStackTrace();
        }
        printnonterminal();
        printtmpterminal();
        printtmpnonterminal();
        printfirstset();
    }
    
    private void maketmppartnonterminal() {
         for(int i = 0; i < tmplinenumber; i++) {                //初始化firstset
            StringBuffer sb = new StringBuffer("");
            if(tmpnonterminal[i].charAt(0) == '<') {
                int j = 1;
                sb.append('<');
                while(tmpnonterminal[i].charAt(j) != '>') {
                    sb.append(tmpnonterminal[i].charAt(j));
                    j++;
                }
                sb.append('>');
            } else if (tmpnonterminal[i].charAt(0) == '\"') {
                int j = 1;
                sb.append('\"');
                 while(tmpnonterminal[i].charAt(j) != '\"') {
                    sb.append(tmpnonterminal[i].charAt(j));
                    j++;
                }
                sb.append('\"');
            } else if (tmpnonterminal[i].charAt(0) == '\'') {
                int j = 1;
                sb.append('\'');
                while(tmpnonterminal[i].charAt(j) != '\'') {
                    sb.append(tmpnonterminal[i].charAt(j));
                    j++;
                }
                sb.append('\'');
            }
            tmppartnonterminal[i] = sb.toString();              //提取出tmpnonterminal中的第一部分保存到tmppartnonterminal,形式是<...>或“...”
        }
    }

    private void maketmpallnonterminal() {
        for(int i = 0; i < tmplinenumber; i++) {                //初始化firstset
            int j = 0;
            while(j < tmpnonterminal[i].length()) {
                StringBuffer sb = new StringBuffer("");
                if(tmpnonterminal[i].charAt(j) == '<') {
                    sb.append('<');
                    j++;
                    while(tmpnonterminal[i].charAt(j) != '>') {
                        sb.append(tmpnonterminal[i].charAt(j));
                        j++;
                    }
                    sb.append('>');
                } else if (tmpnonterminal[i].charAt(j) == '\"') {
                    sb.append('\"');
                    j++;
                     while(tmpnonterminal[i].charAt(j) != '\"') {
                        sb.append(tmpnonterminal[i].charAt(j));
                        j++;
                    }
                    sb.append('\"');
                } else if (tmpnonterminal[i].charAt(j) == '\'') {
                    sb.append('\'');
                    j++;
                    while(tmpnonterminal[i].charAt(j) != '\'') {
                        sb.append(tmpnonterminal[i].charAt(j));
                        j++;
                    }
                    sb.append('\'');
                } else { j++; continue; }
                tmpallnonterminal[i].add(sb.toString());
                j++;
            }
        }
    }

    public void Islegal() {
        for(int i = 0; i < tmplinenumber; i++) {
            for(int j = 0; j < tmplinenumber; j++) {
                if(i != j && tmppartnonterminal[i].equals(tmppartnonterminal[j]) && tmpterminal[i].equals(tmpterminal[j])) {
                    System.out.println("该文法存在左公因子，不符合LL1文法！");
                    System.exit(0);
                }
            }
        }
        
        for(int i = 0; i < tmplinenumber; i++) {                
            if(tmppartnonterminal[i].equals(tmpterminal[i])) {              //表达式左边与表达式右边的第一部分相同
                for(int j = 0; j < tmplinenumber; j++) {
                    if(i != j && !tmppartnonterminal[j].equals(tmpterminal[j]) && tmpterminal[i].equals(tmpterminal[j])) {
                        System.out.println("该文法存在直接左递归，不符合LL1文法！");
                        System.exit(0);
                    }           
                }
            }
        }
        
        //构造有向图，先删除入度为0的节点，并把该节点的下一个节点的入度减一，最后如果还有节点剩下说明存在回路，即存在左递归
        int [][]G = new int[linenumber + 1][linenumber + 1];
        int []indegree = new int[linenumber + 1];
        for(int i = 0; i < tmplinenumber; i++) {
            int pos1 = 0, pos2 = 0, j = 0, k = 0;
           for(j = 0; j <= linenumber; j++) {
              if(nonterminal[j].equals(tmpterminal[i])) { pos1 = j; break; }
           }
           for(k = 0; k <= linenumber; k++) {
              if(nonterminal[k].equals(tmppartnonterminal[i])) { pos2 = k; break; }
           }
           if(k > linenumber) { continue; }
           G[pos1][pos2] = 1;
           indegree[pos2]++;
        }
        for(int i = 0; i <= linenumber; i++) {
            int j = 0;
            while(j <= linenumber && indegree[j] != 0) { j++; }
            if(j > linenumber) {
                System.out.println("该文法存在间接左递归，不符合LL1文法！");
                System.exit(0);
            } else {
                    indegree[j] = -1;
                    for(int k = 0; k <= linenumber; k++) {
                        if(G[j][k] != 0) { indegree[k]--; }
                    }   
            }
        }
        for(int i = 0; i <= linenumber; i++) {
            if(indegree[i] != -1) {
                System.out.println("该文法存在间接左递归，不符合LL1文法！");
                System.exit(0);
            }
        }
    }
    
    public void makefirstset() {
        maketmpallnonterminal();
        printtmpallnonterminal();
        for(int i = 0; i < tmplinenumber; i++) {                //初始化firstset
            int flag = 0;
            for(int j = 0; j <= linenumber; j++) {
                if(tmppartnonterminal[i].equals(nonterminal[j])) { flag = 1; break; }
            }

            if(flag == 0) {
                for(int j = 0; j <= linenumber; j++) {
                    //System.out.println("tmpterminal[i]为" + tmpterminal[i] + ", nonterminal[j]为" + nonterminal[j]);
                    if(tmpterminal[i].equals(nonterminal[j])) { 
                        firstset[j].add(tmppartnonterminal[i]); 
                        endcharacter.add(tmppartnonterminal[i]);
                    }
                }
            }
        }
        printendcharacter();
        while(true) {               //多次扫描，直到firstset不再发生变化
            int flag = 0, end = 0;
            for(int i = 0; i < tmplinenumber; i++) {                //遍历tmpterminal
                if(tmpterminal[i].equals(tmppartnonterminal[i])) { continue; }
                else {              //tmppartnonterminal中的字符不是终结字符
                    Iterator<String> it = tmpallnonterminal[i].iterator();
                    while(it.hasNext()) {
                        String itnext = it.next();
                        int j;
                      
                        for(j = 0; j <= linenumber; j++) {
                            if(itnext.equals(nonterminal[j])) {
                                if(endcharacter.contains(itnext)) { firstset[i].add(itnext); flag = 1; end = 1; break; }
                                Iterator<String> it1 = firstset[j].iterator();
                                while(it1.hasNext()) { firstset[i].add(it1.next()); flag = 1; }
                                if(!firstset[j].contains("")) { end = 1;}
                                break;
                            }
                        }
                        if(end == 1) { break; }
                    }
                }
            }
            if(flag == 1) break;
        }
                    
                    
                    
                    /*if(tmppartnonterminal[i].equals("")) {              //存在空
                        for(int j = 0; j < tmplinenumber; j++) {
                            if(tmppartnonterminal[j].equals(tmpterminal[i])) {
                                Iterator<String> it = tmpallnonterminal[j].iterator();
                                while(it.hasNext()) { 
                                    String itnext = it.next();
                                    int k;
                                    for(k = 0; k < tmplinenumber; k++) {
                                       if(tmpterminal[k].equals(itnext)) {
                                           Iterator<String> it1 = firstset[k].iterator();
                                           while(it1.hasNext()) {
                                               String itnext1 = it1.next();
                                               if(!itnext1.equals("")) {
                                                   firstset[j].add(itnext1);
                                                   break;
                                               }
                                           }
                                       }
                                    }
                                    if(k == tmplinenumber) { 
                                        firstset[j].add(itnext);
                                    }
                                }
                            }
                        }
                    }*/
                    
                    
                    
                    
                    
                    
                    /*int tag = 0;
                    for(int j = 0; j <= linenumber; j++) {
                        if(tmppartnonterminal[i].equals(nonterminal[j])) {
                            second = j;
                            tag = 1;
                            break;
                        }
                    }
                    if(tag == 0) { continue; }
                    for(int j = 0; j <= linenumber; j++) {
                        if(tmpterminal[i].equals(nonterminal[j])) {
                            first = j;
                            break;
                        }
                    }
                    Iterator<String> it = firstset[second].iterator();
                    while(it.hasNext()) {
                        String itnext = it.next();
                        if(!firstset[first].contains(itnext)) {
                            firstset[first].add(itnext);                //将firstset[second]的元素加入到firstset[first]
                            flag = 1;
                        }
                    }
                }
            }
            if(flag == 0) { break;}
        }*/
    }
    
    private void printnonterminal() {
        System.out.println("nonterminal中的元素为：");
        for(int i = 0; i <= linenumber; i++) {
            System.out.println(nonterminal[i] + " ");
        }
        System.out.println();
    }

    private void printfirstset() {
        System.out.println("firstset中的元素为：");
        int count = 0;
        while(count <= linenumber) {
            Iterator<String> it = firstset[count].iterator();
            while(it.hasNext()) {
                System.out.print(it.next() + " ");
            }
            System.out.println();
            count++;
        }
        System.out.println();
    }

    private void printtmpallnonterminal() {
        System.out.println("tmpallnonterminal中的元素为：");
        int count = 0;
        while(count < tmplinenumber) {
            Iterator<String> it = tmpallnonterminal[count].iterator();
            while(it.hasNext()) {
                System.out.print(it.next() + " ");
            }
            System.out.println();
            count++;
        }
        System.out.println();
    }

    private void printtmpterminal() {
        System.out.println("tmpterminal中的元素为：");
        for(int i = 0; i < tmplinenumber; i++) {
            System.out.println(tmpterminal[i] + " ");
        }
        System.out.println();
    }

    private void printtmpnonterminal() {
        System.out.println("tmpnonterminal中的元素为：");
        for(int i = 0; i < tmplinenumber; i++) {
            System.out.println(tmpnonterminal[i] + " ");
        }
        System.out.println();
    }
    
    private void printtmppartnonterminal() {
        System.out.println("tmppartnonterminal中的元素为：");
        for(int i = 0; i < tmplinenumber; i++) {
            System.out.println(tmppartnonterminal[i] + " ");
        }
        System.out.println();
    }
    
    private void printendcharacter() {
        System.out.println("endcharacter中的元素为：");
        Iterator<String> it = endcharacter.iterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }

}
